
import math
from collections import Counter

def knn_classify(train_data, train_labels, test_point, k):
    distances = []
    for i, data_point in enumerate(train_data):
        distance = math.sqrt(sum((dp - tp) ** 2 for dp, tp in zip(data_point, test_point)))
        distances.append((distance, train_labels[i]))

    distances.sort(key=lambda x: x[0])
    k_nearest_neighbors = distances[:k]

    neighbor_classes = [label for _, label in k_nearest_neighbors]
    most_common_class = Counter(neighbor_classes).most_common(1)[0][0]

    return most_common_class

train_features = [
    [5.1, 3.5, 1.4, 0.2],
    [4.9, 3.0, 1.4, 0.2],
    [5.0, 3.4, 1.4, 0.2],
    [7.0, 3.2, 4.7, 1.4],
    [6.4, 3.2, 4.2, 1.5],
    [6.9, 3.1, 4.9, 1.7],
    [6.3, 3.3, 6.0, 2.1],
    [5.8, 2.7, 5.1, 1.9],
    [7.1, 3.0, 5.9, 2.0]
]
train_labels = [
    'Setosa', 'Setosa', 'Setosa',
    'Versicolor', 'Versicolor', 'Versicolor',
    'Virginica', 'Virginica', 'Virginica'
]

test_sample = [5.5, 3.7, 1.5, 0.2]
k_value = 3
predicted_class = knn_classify(train_features, train_labels, test_sample, k_value)

print(f"Predicted Class for {test_sample}: {predicted_class}")
